\section{Introduction}\label{sec:gre}

A \emph{referring expression} (RE) is an expression that 
unequivocally identifies the intended target to the interlocutor, from a set of possible distractors, in a given situation.  
For example, if we intend to identify a certain animal $d$ from a picture of pets, the expression 
``the dog'' will be an RE if $d$ is the only dog in the picture, and if we are confident
that our interlocutor will identify $d$ as a dog. 

The generation of referring expressions (GRE)  is a key task of most natural 
language generation (NLG) systems~\cite{dale2000}. 
Depending on the information available to the NLG system, certain objects might 
not be associated with an identifier which can be easily recognized by the user. 
In those cases, the system will have to generate a, possibly complex, description that contains 
enough information so that the interlocutor will be able to identify the intended referent.
The generation of referring expressions is a well developed field in automated natural language generation building upon GRE foundational work~\cite{winograd,dale89cooking,Dale1995}. 

Low complexity algorithms for the generation 
of REs have been proposed~\cite{arec2:2008:Areces,arec:usin11}. These algorithms are based on variations of the partition refinement algorithms of~\cite{paig:thre87}.
The information provided by a given scene is interpreted as a relational model whose 
objects are classified into sets that fit the same description.  
This classification is successively \emph{refined}  till the target 
is the only element fitting the description of its class.  The existence of an RE 
depends on the information available in the input scene, and on the expressive power of the formal 
language used to describe elements of the different classes in the refinement. 

%The idea of using a formal language to describe the information that an RE should convey has been discussed 
%already in~\cite{Krahmer2003,gardent07:_gener_bridg_defin_descr}.  In~\cite{arec2:2008:Areces,arec:usin11} the 
%combination of partition refinement algorithms and different formal languages is used to classify existing 
%GRE approaches in an expressiveness hierarchy.  For instance, the classical Dale and Reiter algorithms
%compute purely conjunctive formulas; \cite{deemter02:_gener_refer_expres} extends this language by
%adding the other propositional connectives, whereas~\cite{dale91:_gener_refer_expres_invol_relat} extends it by
%allowing existential quantification.

Existing GRE algorithms can effectively compute REs for all individuals in the domain, at the same time. The algorithms always terminate returning a formula of the formal language chosen that uniquely describes the target. 
However, GRE algorithms require a ranking of the properties that are to be used in the referring expressions, and the naturalness of the generated REs strongly depends on this ranking. \cite{arec:2012:coling12} show that a refinement algorithm using the description language \el as formal language is capable of generating 75\% of the REs present in the dataset described in~\cite{viet:gene11}. In this paper we perform a human evaluation of the REs generated by this algorithm on two new corpora and show that even when the generated REs do not coincide with those found in corpora, people actually prefer the REs generated by the system in 92\% of the cases.  

The rest of the paper is structured as follows. In Section~\ref{sec:algorithm} we introduce the technical details of the 
refinement algorithm and explain how it uses the ranking of properties. In this section, we assume that this list is provided as 
input to the algorithm. In Section~\ref{sec:learning}, we show how to estimate the probability of use of a property from corpora in order to obtain the ranking of properties. Given corpora consisting of pairs (scene, target) together with the REs used to 
describe the target in each case, we propose a method to compute the probability of use of each property for each scene, and use a machine learning approach to generalize this approach to new targets and scenes not appearing in the corpora. Section~\ref{sec:evaluation} presents an automatic evaluation and a human evaluation of the generated REs. In Section~\ref{sec:discussion} we discuss related work and analyze the structure of the refinement algorithm in relation to the work of~\cite{keysar:Curr98}, on the egocentric basis of language generation. 

